import java.util.*;

public class Solution2 {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 1. 针对字符串进行排序，作为用于分组的 key
        Map<String, List<String>> map = new HashMap<>();
        for(int i = 0; i < strs.length; i++){
            String key = insertSort(strs[i]);
            if(!map.containsKey(key)){
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(strs[i]);
        }
        List<List<String>> ret = new ArrayList<>();
//        for(String s : map.keySet()){
//            ret.add(map.get(s));
//        }
        for(Map.Entry<String, List<String>> entry : map.entrySet()){
            ret.add(entry.getValue());
        }
        return ret;
    }
    private String insertSort(String str){
        char[] chArr = str.toCharArray();
        for(int i = 1; i < chArr.length; i++){
            char tmp = chArr[i];
            int j = i - 1;
            for(; j >= 0; j--){
                if(tmp < chArr[j]){
                    chArr[j + 1] = chArr[j];
                }else{
                    break;
                }
            }
            chArr[j + 1] = tmp;
        }
        return new String(chArr);
    }
}
